package recursion

func Permutation(str string) []string {
	ans := []string{}
	var fn = func(pStr string){
		ans = append(ans, pStr)
	}
	PermutationProcess([]byte(str), 0, fn)
	return ans
}

func PermutationProcess(strs []byte, index int, fn func(string)){
	if index == len(strs) {
		fn(string(strs))
		return
	}
	for i:= index; i<len(strs); i++ {
		Swap(strs, i, index)
		PermutationProcess(strs, index+1, fn)
		Swap(strs, i, index)
	}
}

func Swap(strs []byte, i, j int){
	strs[i], strs[j] = strs[j], strs[i]
}

func PermutationWithoutRepeat(str string) []string {
	ans := []string{}
	var fn = func(pStr string){
		ans = append(ans, pStr)
	}
	PermutationProcess1([]byte(str), 0, fn)
	return ans
}

func PermutationProcess1(strs []byte, index int, fn func(string)){
	if index == len(strs) {
		fn(string(strs))
		return
	}
	visit := make([]bool, 26)
	for i:= index; i<len(strs); i++ {
		if !visit[strs[i]-'a'] {
			visit[strs[i]-'a'] = true
			Swap(strs, i, index)
			PermutationProcess1(strs, index+1, fn)
			Swap(strs, i, index)
		}
	}
}